数学超苦手な文系エンジニアがAtCoder Beginner Contest 268に参加してみました

今泉大樹

2022.09.13

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。

皆さんはアルゴリズムと数学に強くなりたいですか？

私はなりたいです。

私は以前よりAtCoderという競技プログラミングのサービスでコンテストに出て学習をしております。(前回のコンテストの出場の際に書いた記事はこちらです)

今回も 9/10に開催されたユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)に参加させて頂きましたので、個人的に学べたことを含めて記事を書かせていただきました!

前置き・事前知識

こちらの記事の前置き・事前知識をご参照ください。(見ていただきたい内容が増えたらこちらを更新させていただきます)

想定される読者の方について

こちらも、前回の記事の段階から変わっておりませんのでご参照ください。 (競プロ中級者以上の方であれば、特に学べることも刺激を受けられることも無いかもしれませんのでご了承ください)

コンテスト参加結果

以下のように目標を設定しておりますが、今回も(前回と同様)最低目標の2問を正解するところまででした。

最低目標: A・Bの2問を解く
チャレンジ目標: C問題(もしくはD問題)を解く

ただし今回はC問題を正解出来た方が少なかったようで、結果的に簡単なC問題を解けた時と同じくらいレートを向上させることができました!

atcoder_bun913_20220910_rate

A問題 Five Integers

与えられる 5 つの整数 A,B,C,D,E の中に何種類の整数があるかを出力してください。

5つの要素の種類数を出力させれば良いと言うことですね。

Pythonにはset型という集合演算を扱える型がありますので、それを利用すればlistの重複排除的な使い方でも便利です。

以下が私が提出したコードです(43秒ほどで提出)

L = list(map(int, input().split()))
print(len(set(L)))

B問題 Prefix?

英小文字のみからなる 2 つの文字列 S,T が与えられます。 S が T の接頭辞かどうかを判定してください。

Pythonの文字列型に対して、startswithという関数を利用できます。(ドキュメント: 組み込み型 — Python 3.10.6 ドキュメント)

Sの文字数までTを見ると言った方法でも良いと思います。

以下が私が提出したコードです(A問題提出から1分40秒ほどで提出)

S = input()
T = input()
is_start = T.startswith(S)

if is_start is True:
    print("Yes")
    exit()
print("No")

C問題 Chinese Restaurant

前回のC問題についてのまとめでも記載しておりますが、今回も何も考えずに以下の様に二重forループを記載すると、制限時間内に処理が終わらず、正解できません。

from collections import deque

N = int(input())
P = list(map(int, input().split()))
q = deque(P)
ans = 0
# N-1回料理を回転させる
for i in range(N):
    s = 0
    # 料理を回転させた結果、何人が満足できるか数え上げる
    for j, p in enumerate(q):
        cur = p + N
        if (cur - 1) % N == j or cur % N == j or (cur + 1) % N == j:
            s += 1
    ans = max(ans, s)
    q.rotate(1)
print(ans)

Nが最大で2×10の5乗と非常に大きく、二重ループだと 10の10乗を超える計算量となってしまうためです。(参考: EX21 - 計算量の見積もり)

この辺りの操作回数についても公式解説で触れてくれております。

なお、私はこの問題を見てアプローチがさっぱりわかりませんでしたが、公式の解説動画でわかりやすく説明してくださっております。

料理 And 回す回数 を中心に考えていく様にするとのことです。

以下の様な表を書いていくことで、私にとってわかりやすくなっていきました。

abc268c_step1

必要な情報は「料理を回転させていき、喜ぶ人の数」を求めることなので、以下の様にデータを保有するようにします。

abc268c_step2

最終的に自分で理解できる範囲で記載したコードがこちらです(コンテスト終了後に提出。他の方のコードも参考にさせていただきました。)

N = int(input())
P = list(map(int, input().split()))

C = [0 for _ in range(N)]
# C[i] = i回動かした時に喜ぶ人の数(集計表)
for i, p in enumerate(P):
    # Piと人が一致しているか、その左右にある時が嬉しい
    # indが料理が望む人のちょうど前に来るための回数
    ind = (p - i) % N
    C[(ind - 1) % N] += 1
    C[ind] += 1
    C[(ind + 1) % N] += 1
print(max(C))